2.1 Función de las seis jorobas de camello:
La función de las seis jorobas de camello (Six-Hump Camel) es una función frecuentemente utilizada para evaluar el desempeño de algoritmos de optimización en espacios de búsqueda no triviales. es una función no convexa, multimodal y polinómica de grado cuatro.
Se define como:
\[ f(\mathbf{x}) = \left( 4 - 2.1x_1^2 + \frac{x_1^4}{3} \right)x_1^2 + x_1x_2 + \left( -4 + 4x_2^2 \right)x_2^2 \]
La función presenta seis regiones prominentes (jorobas) en su superficie, siendo esta una función no convexa, dando lugar a múltiples mínimos locales y dos mínimos globales bien definidos. Simon Fraser University. (s.f.).
Para esta definición:
-La primera parte de la función, depende de x1 y genera curvaturas multiples.
-La segunda parte de la función x1 y x2 es un acoplamiento lineal
-La tercera parte de la función x2 agrega simetría
-Sus dos mínimos globales son (x1,x2)=(0.0898, -0.7126) y (x1,x2)=(-0.0898, 0.7126) con valor aproximado: \[f(x_1, x_2) \approx -1.0316\]
Representación más gráfica de la función con sus jorobas:
Fig 9. Función Six hump camel (2D)
2.2 Optimización mediante descenso del gradiente:
Para gráficar y un entendimiento más fácil x1 = x y x2 = y
Así:
\[ f(x, y) = \left(4 - 2.1\, x^2 + \frac{x^4}{3}\right)x^2 + x\,y + \left(-4 + 4\, y^2\right)y^2 \]
Gradiente de la función:
El gradiente es el vector de derivadas parciales: \[ \nabla (x, y) = \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) \] - La derivada con respecto a x es: \[ \frac{\partial f}{\partial x} = 8x - 8.4x^3 + 2x^5 + y \] - La derivada con respecto a y es: \[ \frac{\partial f}{\partial y} = x + 16y^3 - 8y \]
Método de descenso por gradiente en dos dimensiones:
Fig 10. Descenso por gradiente Six hump camel (2D)
## iter x y f
## 240 239 -0.08709228 0.7123408 -1.031599
## 241 240 -0.08715570 0.7123481 -1.031600
## 242 241 -0.08721767 0.7123552 -1.031602Figura 10:
En la figura podemos observar el método de descenso por gradiente, un algoritmo de optimización iterativo que busca encontrar el mínimo de una función diferenciable. Consiste en calcular el gradiente, que indica la dirección de mayor incremento, y actualizar los parámetros en sentido opuesto, es decir, moviéndose hacia la dirección de mayor descenso—mediante una tasa de aprendizaje que regula el tamaño de cada paso. Este proceso se repite hasta que las actualizaciones son mínimas.(IBM, s.f.)
- En esta representación gráfica podemos observar que partiendo desde un punto aleatorio del plano, el descenso por gradiente generalmente busca el minimo local más cercano, en este caso encontró uno de los dos minimos globales que tiene esta función ubicado en (x,y)=(-0.0898, 0.7126)
- El descenso por gradiente puede o no encontrar el valor óptimo global de la función de las seis jorobas de camello, ya que este se “guiará” por el minimo local más cercano. Así que depende mucho de su condición inicial, en este caso, aleatoria.
Método de descenso por gradiente en tres dimensiones:
Fig 11. Descenso por gradiente Six hump camel (3D)
Figura 11:
- En tres dimensiones podemos ver una condición inicial diferente a la del gráfico en dos dimensiones. Esta condición inicial aleatoria se generó más cerca del minimo local (x,y)=(−0.08984, 0.71266) por lo tanto, el descenso por gradiente va a este punto mínimo local y no a uno de los minimos globales.
“La función Six Hump Camel posee seis mínimos locales, de los cuales dos son mínimos globales. Este comportamiento multimodal la hace especialmente útil como caso de prueba en estudios y algoritmos de optimización, ya que permite evaluar la capacidad de estos para evitar converger únicamente en mínimos locales no globales.” (Simon Fraser University, s.f.).
- La línea azul ilustra el recorrido desde el punto de partida en el plano xyz hasta el mínimo local obtenido por el descenso por gradiente. Aunque es un mínimo, no es el global, lo que significa que existen otros puntos donde la función toma un valor inferior que sí son totalmente óptimos
2.3.1 Optimización con el método de enjambre de particulas PSO en dos dimensiones:
Fig 12. Método de enjambre de particulas (PSO) (2D)
Figura 12:
En la figura se puede observar el proceso de optimización por enjambre de particulas en dos dimensiones en el cual en este caso se generaron 50 particulas en posiciones aleatorias dentro del dominio y cada particula con una velocidad inicial aleatoria
El algoritmo PSO guía mediante un equilibrio entre exploración y explotación. Es decir, cada partícula se mueve en el espacio de búsqueda basándose en tres componentes:
-Inercia: Conserva una parte de su velocidad actual.
-Atracción personal (pbest): Se dirige hacia la mejor posición que ha encontrado.
-Atracción social (gbest): Se mueve hacia la mejor posición encontrada por todo el enjambre.
En el proceso, cuando alguna partícula descubre una buena solución (un valor bajo de la función en nuestro problema de minimización), esa posición se convierte en el “global best”. Una vez que se determina un gbest, las demás partículas se ven atraídas hacia esa región, lo que provoca que eventualmente converjan entorno a esa solución. Huang, H., Qiu, J., & Riedl, K. (2023).
En este caso el gbest (global best) ubicado en (x,y)=(-0.0898, 0.7126) quien es el que se identifica como el primer óptimo de la función en esta condición aleatoria en especifico.
2.3.2 Optimización con el método de enjambre de particulas PSO en tres dimensiones:
Fig 13. Método de enjambre de particulas (PSO) (3D)
Figura 13:
En esta representación en tres dimensiones con una condición inicial aleatoria diferente a la de dos dimensiones, las particulas convergen en el segundo minimo global que posee la función de las seis jorobas de camello, exactamente en (x,y,z)=(0.0898, -0.7126, 0) en este caso, el minimo global óptimo. El cambio a tres dimensiones no supuso una diferencia mayor a su comportamiento comparado al de dos dimensiones.
2.3.3 Optimización con el método de evolución diferencial DE en dos dimensiones:
Fig 14. Método de evolución diferencial (DE) (2D)
Figura 14:
En la figura se usa como método de optimización el algoritmo de evolución diferencial DE el cual se caracteriza por utilizar una población de soluciones candidatas que evolucionan mediante operadores de mutación, cruce (recombinación) y selección. A diferencia de otros algoritmos evolutivos, DE genera nuevas soluciones perturbando vectores existentes mediante diferencias escaladas entre otros miembros de la población. Storn, R., & Price, K. (1997).
Esto quiere decir que el algoritmo de evolución diferencial sirve para encontrar los mejores valores posibles de la función, en este caso sus dos minimos globales que posee.
Para entender la figura y el algoritmo se tiene que: - Primero, se asigna aleatoriamente una población o candidatos dentro del dominio de la función.
- Luego, en cada iteración del algoritmo DE cada agente crea una versión modificada del mismo, que se mezcla con otros tres agentes/miembros de la población al azar en cualquier parte del plano.
- Este agente mutado se mezcla con el agente original, mezclando su información. Si esta información se define como un punto más bajo en el plano, este lo reemplaza, si no, el antiguo se queda.
- El proceso se repite hasta que a través de cada iteración (generaciones) el grupo se va acercando cada vez al punto más bajo, en este caso el minimo global. Storn, R., & Price, K. (1997).
En la figura se puede percibir que en menos de 50 iteraciones se llegó a los dos minimos globales, además de como cada punto rojo (población) se cruzaba y mutaba para encontrar estos mínimos.
De los anteriores algoritmos de optimización DE es el único quien logró encontrar los dos mínimos globales de la función de las seis jorobas de camello.
2.3.4 Optimización con el método de evolución diferencial DE en tres dimensiones:
Fig 15. Método de evolución diferencial (DE) (3D)
Figura 15:
En tres dimensiones se amplía la búsqueda y adaptación de la Evolución Diferencial a un espacio de mayor dimensión, introduce operaciones vectoriales en tres componentes Cada candidato es ahora un vector (x,y,z) y proporciona una visualización que proyecta información de la tercera dimensión a través del color. Los pasos fundamentales (mutación, cruce y selección) se mantienen, pero se ejecutan en un espacio más complejo. También se nota a medida de cada iteración como cambia el color en los agentes y descienden a los dos minimos globales hasta llegar al 0 en z.
2.3.5 Optimización con el método GA de algoritmos evolutivos en 2D
Fig 16. Método de algoritmos geneticos (GA) (2D)
Figura 16:
Los Algoritmos Genéticos (Genetic Algorithms) son técnicas de optimización inspiradas en el proceso de evolución natural. Al igual que la selección natural en la biología, simulan cómo evolucionan las soluciones “mejores” con el tiempo. Holland, J. H. (1975).
En este caso, el algoritmo se prueba con 50 individuos dentro de la población los cuales son representados por cada punto generado en la figura de manera aleatoria. A cada punto se le asigna un “valor” evaluando su función de aptitud o “fitness” (en esta situación se usa la función negativa porque se quiere encontrar es el minimo)
- Los “puntos” escogidos son aquellos con menor valor(según esta situación ya que se busca encontrar el minimo)
- Estos “puntos” o individuos dentro de la población que ya fueron elegidos, se cruzan y dan lugar a hijos con mejores caracteristicas, esto, sucediendo de generación en generación mejorando con cada iteración.
Esto da lugar a que el algoritmo encuentre el minimo global optimo según las generaciones.
2.3.6 Optimización con el método GA de algoritmos evolutivos en 3D
Fig 17. Método de algoritmos geneticos (GA) (3D)
2.4 Conclusiones:
¿Qué aportaron los métodos de descenso por gradiente y qué aportaron los métodos heurísticos?
Método por descenso del gradiente:
En la figura 10 donde se hace el recorrido del método de descenso por gradiente con condición inicial aleatoria en dos dimensiones, se aprecia que para alcanzar el valor objetivo f(x,y)≈−1.0316 tomó 241 iteraciones exactamente, Esto, solo en el caso de esta seed ya que en el caso de recorrido del algoritmo en tres dimensiones (figura 11) el método de descenso por gradiente se atascó en uno de los mínimos locales que posee la función de las seis jorobas de camello. Por lo tanto este método requiere condiciones especiales para que encuentre el valor objetivo óptimo porque depende de que tan cerca la condición aleatoria esté a uno de los dos minimos globales o minimos locales de la función para que descienda a estos.
Métodos heurísticos:
Optimización con el método de algoritmos evolutivos (GA):
Usando el método de algoritmos evolutivos (GA) para una población de 50 individuos, en dos dimensiones y tres dimensiones se llegó a la conclusión que en la generación numero 17 el algoritmo pudo alcanzar el valor objetivo de la función sin atascarse en mínimos locales. Se tiene en cuenta también que no converje al mismo tiempo en los dos minimos globales que tiene la función si no al primero que encuentra.
Optimización con el método de enjambre de particulas (PSO):
Por optimización mediante PSO se alcanzó el valor objetivo por primera vez a partir de la iteración 18 (con una población de 50 y una inercia de 0.5) la cual a partir de esta iteración se presenta un mejor fitness igual a −1.0316. En todos los casos de condición aleatoria el enjambre de particulas llegó a uno de los dos minimos globales.Por lo tanto, se concluye a partir de esto que:
- En dos y tres dimensiones el algoritmo PSO siempre encontró el valor objetivo, pero no los dos mínimos globales al mismo tiempo que presenta la función de las seis jorobas de camello.
- Con un ajuste de la inercia en el algoritmo a 0.5 se logró que todas las particulas converjan al primer minimo global encontrado por una de ellas.
- A comparación del algoritmo de descenso por gradiente, la optimización por PSO si va exactamente a el valor óptimo de la función sin tener en cuenta una condición inicial aleatoria que lo beneficie.
Optimización con el método de evolución diferencial (DE):
Por optimización mediante DE se logró el valor objetivo en alrededor de 43 iteraciones con una población de 50 individuos. Tanto como en dos dimensiones y tres dimensiones el algoritmo encontró los dos mínimos globales de la función de una forma eficiente, dejando pasar mínimos locales y encontrando el valor óptimo de la función. A diferencia de los otros métodos heuristicos y metodo por descenso del gradiente presentados en este trabajo, el algoritmo de evolución diferencial fue el único en encontrar los dos mínimos globales de la función de las seis jorobas de camello